package src.CodeTop;

/**
 * 反转链表II
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 *  
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4,5], left = 2, right = 4
 * 输出：[1,4,3,2,5]
 * 示例 2：
 *
 * 输入：head = [5], left = 1, right = 1
 * 输出：[5]
 */

public class _92ReverseLinkedListII {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        ListNode head = TestListNode.generateLinkedList(5, arr);
        ListNode target = reverseBetween(head, 2, 4);
        TestListNode.showLinkedList(target);
    }

    public static ListNode reverseBetween(ListNode head, int left, int right) {
        // 虚拟头结点(防止左边界为1的时候，第一个结点前无结点)
        ListNode virNode = new ListNode(0);
        // 记录虚拟头结点，方便最后返回
        ListNode mark = virNode;
        // 连接到原链表之前
        virNode.next = head;
        // 记录需要反转的结点个数
        int count = right - left + 1;
        // 遍历到需要反转的左边界的前一个结点
        for (int i = 0 ; i < left - 1 ; i++) {
            virNode = virNode.next;
        }
        // 然后以当前的结点为头结点，反转count个结点
        virNode.next = reverse(virNode.next, count);
        // 返回虚拟头结点的下一个结点
        return mark.next;
    }

    public static ListNode reverse(ListNode head, int n) {
        // 如果反转到最后一个结点则直接返回
        if (n == 1) {
            return head;
        }
        // 递归查找到需要反转的最后两个结点
        ListNode tail = head.next;
        ListNode p = reverse(head.next, n - 1);
        // 依次反转最后两个结点
        head.next = tail.next;
        tail.next = head;
        // 返回新链表的头结点，也即原链表需要反转的最后一个结点，注意，每一层返回的p结点都是一样的
        return p;
    }
}
